//给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
//
// 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
//
//
//
// 示例 1：
//
//
//输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
//输出：4
//解释：最长递增路径为 [1, 2, 6, 9]。
//
// 示例 2：
//
//
//输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
//输出：4
//解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
//
//
// 示例 3：
//
//
//输入：matrix = [[1]]
//输出：1
//
//
//
//
// 提示：
//
//
// m == matrix.length
// n == matrix[i].length
// 1 <= m, n <= 200
// 0 <= matrix[i][j] <= 2³¹ - 1
//
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 记忆化搜索 数组 动态规划 矩阵 👍 771 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function longestIncreasingPath(matrix: number[][]): number {
    /*
    ? 第一步： 从一点往4个方向递归：碰到比他大的就加一，否则就加0，结束返回；
    ? 第二步： 如果当前格子已经算出来过最大值 就直接使用
    ? 第三步： 否则就把往4个方向上走的最大值记录下来给dp
     */
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    const dp = Array.from({length:rowLen},()=>new Array(colLen).fill(0));
    let ans = 0;

    //? 第一步： 从一点往4个方向递归：碰到比他大的就加一，否则就加0，结束返回；
    function helper(i,j,lastNum){
        if(i<0 || j<0 || i>=rowLen || j>=colLen || matrix[i][j] <= lastNum) return 0;
        if(dp[i][j]) return dp[i][j]  //? 第二步： 如果当前格子已经算出来过最大值 就直接使用
        const top = helper(i-1,j,matrix[i][j])+1
        const bottom = helper(i+1,j,matrix[i][j])+1
        const left = helper(i,j-1,matrix[i][j])+1
        const right = helper(i,j+1,matrix[i][j])+1
        dp[i][j] = Math.max(top,bottom,left,right); //? 第三步： 否则就把往4个方向上走的最大值记录下来给dp
        return dp[i][j];
    }

    for(let i=0; i<rowLen; i++) {
        for(let j=0; j<colLen; j++) {
            ans = Math.max(ans,helper(i,j,-1))
        }
    }
    return ans;

};
//leetcode submit region end(Prohibit modification and deletion)
